To perform high-speed information processing, parallel processing apparatuses which simplify individual processes and perform these simplified processes in parallel have been developed. An example is a parallel processing apparatus in which cells each for performing simple processing are arranged in a matrix to form a cell array, and these cells in this cell array are operated in parallel. An application example of this parallel processing apparatus is a processing apparatus (Japanese Patent Laid-Open No. 2001-242771) which includes a fingerprint sensor and fingerprint verification circuit in each cell, and determines whether a fingerprint obtained by the fingerprint sensors by operating all cells in parallel matches a registered fingerprint. Another application example is an apparatus (J. C. Gealow et al., “System Design for Pixel-Parallel Image Processing”, IEEE Transaction on very large scale integration systems, vol. 4, no. 1, 1996) in which each cell has an image processing circuit, and which performs various image processing operations for an image acquired by an optical sensor or the like by operating all the cells in parallel.
The parallel processing apparatus having the cell array as described above will be briefly explained below. In this parallel processing apparatus as shown in FIG. 21, a plurality of cells each having a processing circuit are arranged in a matrix, and perform parallel processing on the basis of data and instructions given from a control circuit. When this parallel processing performed by these cells is completed, the control circuit totalizes processing results output from the processing circuits of the cells to generate and output a total processing result.
When the apparatus includes a large number of cells, the processing circuit in each cell is simplified, and the processing result obtained by the processing circuit in each cell is data of true or false, or data of about a few bits.
An application example in which a parallel processing apparatus having a cell array is often used is image processing. When parallel processing is applied to image processing, each cell performs predetermined processing for a few dots forming an image to be processed. For example, when image processing such as pattern matching is to be performed, each cell performs image processing for dots in an image assigned to the cell, and outputs true, false, or the like as a matching result. When parallel processing of each processing is completed, a control circuit counts and totalizes the number of true outputs, calculates the matching ratio or the like of the image on the basis of the totalized number of true outputs, and generates a pattern matching processing result.
As described above, in a parallel processing apparatus in which a larger number of processing circuits separately disperse, processing results obtained by these processing circuits must be collected. In parallel processing, therefore, if the collecting process such as the totalization of true or false is not fast, the effect of increasing the operation speed by the parallel processing is lost.
The parallel processing apparatus totalization process of collecting processed data includes a first method by which processing results are read out from individual cells and totalized in the same manner as in a DRAM (Dynamic Random Access Memory) or the like. A second method (Japanese Patent Laid-Open No. 2001-166917) is also proposed in which cells each having a variable delay time circuit are connected in series, and delay times of these variable delay circuits during which processing results are output are collectively measured, thereby rapidly totalizing the processing results.
First, the first method of reading out processing results from individual cells and totalizing the readout results in the same manner as in a DRAM or the like will be described below. As shown in FIG. 22, this method uses a plurality of cells 2201 arranged into n rows×m columns. The input of a processing circuit 2202 of each cell 2201 is connected to a select signal line 2203, and the output of each cell 2201 is connected to a data bus 2204. The select signal line 2203 is connected to each row of the arrayed processing circuits 2202, and the data bus 2204 is connected to each column of the arrayed processing circuits 2202.
An address signal generator 2206 in a row selection controller 2205 generates an address signal for sequentially designating different rows one by one, in synchronism with an output clock signal from a clock generator 2210. The address signal thus generated is transmitted to a predetermined select signal line 2203 via a decoding circuit 2207 to select cells in a row corresponding to the select signal line 2203 to which the address signal is transmitted. In this selected row, each processing circuit 2202 outputs a processing result (true or false), and this processing result is input to a selector circuit 2208 via the data bus 2204. Accordingly, processing results are output from a plurality of processing circuits 2202 for each row in synchronism with the row clock signal described above.
The processing results thus output from the processing circuits 2202 are transmitted to the selector circuit 2208 by the data bus 2204. The selector circuit 2208 accepts a plurality of processing results from each row by the data bus 2204, and transmits the accepted processing results to a counter 2209 for each row. The counter 2209 counts the thus transmitted processing results from the processing circuits 2202. The counter 2209 totalizes the processing results (e.g., true) from the processing circuits 2202, and outputs the addition result of these processing results.
As a consequence, the counter 2209 obtains the total of the output processing results (e.g., the number of true outputs) from the processing circuits 2202.
For example, if the arrangement shown in FIG. 22 is so designed that the processing circuit 2202 outputs true when a prerecorded reference pattern matches a detected pattern, a surface (fingerprint) shape detected in the region where the cells 2201 are arranged can be verified. In this case, if the number of cells from which true is output exceeds 80% of all the cells, it is possible to determine (verify) that the detected fingerprint shape matches the prerecorded fingerprint shape. Note that the fingerprint data is the total of the reference patterns of all the cells.
The second method mentioned earlier will be described below. As shown in FIG. 23, each cell 2301 includes a processing circuit 2302 and a variable delay circuit 2303 which changes the passing time of progression in accordance with a processing result from the processing circuit 2302. A plurality of cells 2301 are connected in series via the variable delay circuits 2303. The variable delay circuit 2303 is made up of inverter circuits different in driving force, and an output result (true or false) from the processing circuit 2302 of each cell 2301 is reflected on the signal propagation time of the delay circuit 2303.
When a control circuit 2304 transmits a measurement input signal to the cells 2301 thus connected in series, the transmitted measurement input signal is first input to the variable delay circuit 2303 of the first cell 2301, passes through the variable delay circuits 2303 of the cells 2301, passes through the variable delay circuit 2303 of the last cell 2301, and enters a delay counter 2305 as a measurement output signal.
Assume that the variable delay circuit 2303 gives a predetermined additional delay to the fundamental delay of a passing signal if the processing result from the processing circuit 2302 is true. Accordingly, the measurement output signal passing through all the cells 2301 is input to the delay counter 2305 after being delayed from a fundamental delay time obtained by multiplying the fundamental delay time by the number of all cells, by an additional delay time obtained by multiplying the additional delay by “the number of cells 2301 (the number of true cells) whose processing circuits 2302 output true”. On the other hand, the measurement input signal output from the control circuit 2304 is also output to the delay counter 2305 without passing through the cells 2301.
The delay counter 2305 calculates a difference between the input time of the measurement input signal which is directly input and the input time of the measurement output signal passing through the last cell 2301, and counts the number of true cells 2301 on the basis of this time difference.
The time at which the measurement output signal is input to the delay counter 2305 is delayed from the output time of the measurement input signal by the fundamental delay×the number of cells+the additional delay×the number of true cells, so this delay is measured. Since the fundamental delay, the additional delay, and the number of cells are already known, the number of true cells can be calculated by subtracting the fundamental delay×the number of cells from the measured delay, and dividing this value by the additional delay.
For example, if the arrangement shown in FIG. 23 is so designed that the processing circuit 2302 outputs true when a prerecorded reference pattern matches a detected pattern, a surface (fingerprint) shape detected in the region where the cells 2301 are arranged can be verified. In this case, if the number of cells from which true is output exceeds 80% of all the cells, it is possible to determine (verify) that the detected fingerprint shape matches the prerecorded fingerprint shape. Note that the fingerprint data is the total of the reference patterns of all the cells.
In the first conventional method described previously, however, the processing results from the cells are transferred row by row to the counter, but the counter totalizes the processing results cell by cell. In the first conventional method, therefore, if the number of arrays increases to increase the number of cells, the time required for the totalization prolongs accordingly. For example, when the first method is applied to an apparatus for verifying fingerprints as described above, if the number of cells is increased to raise the accuracy, the time required to totalize true cells prolongs, and this extends the time required for the verification process, and deteriorates the convenience.
Also, in the second method described above, the differences between signal propagation of the inverter circuits different in driving force are used as the variable delay circuits. This makes it difficult to ensure accuracy, and produces an error in the totalization result. For example, when the second method shown in FIG. 23 is applied to an apparatus for performing fingerprint verification, the verification is performed using the number of true cells. If an error occurs in the totalization result, therefore, the verification ratio lowers, and this makes it impossible to assure high security.
Furthermore, in either method described above, totalization cannot be performed for arbitrary ones of a plurality of arrayed cells. Accordingly, when the above conventional techniques are applied to, e.g., fingerprint verification, any portion of a detected fingerprint cannot be compared.
The present invention has been made to solve the above problems, and has as its object to make it possible to totalize processing results from a plurality of cells processed in parallel more rapidly and accurately than in the conventional apparatuses, and to totalize processing results from arbitrary cells.